package com.leetcode.图论;

import java.util.LinkedList;
import java.util.Queue;

//腐烂的橘子
public class lc_994 {
    public static void main(String[] args) {

    }

    public int orangesRotting(int[][] grid) {
        //
        int M = grid.length;
        int N = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        //count 表示新鲜橘子的数量
        int count = 0;
        //遍历二维数组,找出所有新鲜和腐烂的橘子
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (grid[r][c] == 1) {
                    count++;
                    //腐烂的橘子直接放入队列
                } else if (grid[r][c] == 2){
                    queue.add(new int[]{r, c});
                }
            }
        }
        //round表示腐烂的轮数或者分钟数
        int round = 0;
        //如果有新鲜橘子 并且 队列不为空
        //知道上下左右都触及边界或者初始情况腐烂的橘子已经遍历完
        while (count > 0 && !queue.isEmpty()) {
            //BFS层级,过去一分钟了
            round++;
            //拿到当前层级的腐烂橘子数量,因为每个层级会更新队列
            int n = queue.size();
            //遍历当前分钟的队列
            for (int i = 0; i < n; i++) {
                //每拿到一个腐烂的橘子就踢出队列
                int[] orange = queue.poll();
                //得到这个腐烂橘子的坐标
                int r = orange[0];
                int c = orange[1];
                //判断上下左右是否未到边界,并且是新鲜的橘子,就直接感染
                //上
                if(r - 1 >= 0 && grid[r - 1][c] == 1){
                    //进行感染
                    grid[r - 1][c] = 2;
                    //好橘子-1
                    count--;
                    //放入腐烂橘子队列中
                    queue.add(new int[]{r - 1, c});
                }
                //下
                if(r + 1 < M && grid[r + 1][c] == 1){
                    //进行感染
                    grid[r + 1][c] = 2;
                    //好橘子-1
                    count--;
                    //放入腐烂橘子队列中
                    queue.add(new int[]{r + 1, c});
                }
                //左
                if(c - 1 >= 0 && grid[r][c - 1] == 1){
                    //进行感染
                    grid[r][c - 1] = 2;
                    //好橘子-1
                    count--;
                    //放入腐烂橘子队列中
                    queue.add(new int[]{r, c - 1});
                }
                //右
                if(c + 1 < N && grid[r][c + 1] == 1){
                    //进行感染
                    grid[r][c + 1] = 2;
                    //好橘子-1
                    count--;
                    //放入腐烂橘子队列中
                    queue.add(new int[]{r, c + 1});
                }
            }
        }
        //如果此时还有健康的橘子,返回 -1,否则返回层级
        return count > 0 ? -1 : round;
    }
}
